Papers with memory complexity
Lil: Less is Less When Applying Post-Training Sparse-Attention Algorithms in Long-Decode Stage (2026.findings-acl)
Copied to clipboard
Junhao Hu, Fangze Li, Mingtao Xu, Feifan Meng, Shiju Zhao, Tiancheng Hu, Ting Peng, Anmin Liu, Wenrui Huang, Chenxu Liu, Ziyue Hua, Tao Xie
| Challenge: | Prior work typically decomposes inference into prefill and decode stages, with the decode stage dominating total latency. |
| Approach: | They propose an algorithm that detects threshold where information loss exceeds information gain during sparse decoding to reduce token consumption by up to 90% and a marginal accuracy degradation of less than 2%. |
| Outcome: | The proposed algorithm reduces token consumption by 90% with a marginal accuracy degradation of less than 2% across reasoning-intensive benchmarks. |
H-Transformer-1D: Fast One-Dimensional Hierarchical Attention for Sequences (2021.acl-long)
Copied to clipboard
| Challenge: | Existing hierarchical methods to compute attention are superior to sub-quadratic ones . a particular type of attention, called multi-head scaled dot-product attention, is one of the main components of the Transformer architecture . |
| Approach: | They propose a hierarchical method to compute attention in the Transformer architecture . they perform extensive experiments to show that it captures hierarchic structure in sequences . |
| Outcome: | The proposed method outperforms sub-quadratic models on the Long Range Arena benchmark by over +6 points on average. |
ResFormer: All-Time Reservoir Memory for Long Sequence Classification (2025.emnlp-main)
Copied to clipboard
| Challenge: | Existing models with quadratic time and memory complexity restrict input length . however, analyzing extensive sequential contexts is challenging . |
| Approach: | They propose a neural network architecture that captures contextual dependencies in linear time and a nonlinear readout to model short-term dependencies within sentences. |
| Outcome: | The proposed model outperforms baseline models on EmoryNLP datasets and on IEMOCAP and MultiWOZ datasets. |
Sparsifying Transformer Models with Trainable Representation Pooling (2022.acl-long)
Copied to clipboard
| Challenge: | Existing approaches to sparsify attention in the Transformer model are based on quadratic memory complexity and a lack of information for each word. |
| Approach: | They propose a method to sparsify attention in a Transformer model by learning to select the most-informative token representations during the training process. |
| Outcome: | The proposed model performs better than the current SOTA model while being 1.8 faster during training, 4.5 faster inference and 13 more efficient in the decoder. |
Fine-Tuning Pre-trained Transformers into Decaying Fast Weights (2022.emnlp-main)
Copied to clipboard
| Challenge: | Autoregressive Transformers incur O(T) complexity during per-token generation due to the self-attention mechanism. |
| Approach: | They propose a kernel-based method to approximate causal self-attention by replacing it with recurrent formulations with various update rules and feature maps to achieve O(1) time and memory complexity. |
| Outcome: | The proposed method outperforms prior methods and retains 99% of attention’s performance on WikiText-103 against more complex attention substitutes. |
RWKV: Reinventing RNNs for the Transformer Era (2023.findings-emnlp)
Copied to clipboard
Bo Peng, Eric Alcaide, Quentin Anthony, Alon Albalak, Samuel Arcadinho, Stella Biderman, Huanqi Cao, Xin Cheng, Michael Chung, Leon Derczynski, Xingjian Du, Matteo Grella, Kranthi Gv, Xuzheng He, Haowen Hou, Przemyslaw Kazienko, Jan Kocon, Jiaming Kong, Bartłomiej Koptyra, Hayden Lau, Jiaju Lin, Krishna Sri Ipsit Mantri, Ferdinand Mom, Atsushi Saito, Guangyu Song, Xiangru Tang, Johan Wind, Stanisław Woźniak, Zhenyuan Zhang, Qinghua Zhou, Jian Zhu, Rui-Jie Zhu
| Challenge: | recurrent neural networks struggle to match the performance of Transformers due to limitations in parallelization and scalability. |
| Approach: | They propose a model architecture that combines the efficient parallelizable training of transformers with the efficient inference of RNNs. |
| Outcome: | The proposed model performs on par with similarly sized RNNs, suggesting future work can leverage this architecture to create more efficient models. |